/*
 * @lc app=leetcode.cn id=969 lang=cpp
 *
 * [969] 煎饼排序
 */

// @lc code=start
class Solution
{
public:
    void reverse(vector<int> &arr, vector<int> &idxs, int len)
    {
        int i = 0, j = len - 1;
        while (i < j)
        {
            swap(arr[i], arr[j]);
            idxs[arr[i]] = i;
            idxs[arr[j]] = j;
            i++;
            j--;
        }
    }
    vector<int> pancakeSort(vector<int> &arr)
    {
        int n = arr.size();
        vector<int> idxs(n + 1);
        for (int i = 0; i < n; i++)
        {
            idxs[arr[i]] = i;
        }

        vector<int> ans;
        for (int i = n; i >= 1; i--)
        {
            if (idxs[i] == i - 1)
            {
                continue;
            }

            if (idxs[i] + 1 != 1)
            {
                ans.push_back(idxs[i] + 1);
                reverse(arr, idxs, idxs[i] + 1);
            }

            if (i != 1)
            {
                ans.push_back(i);
                reverse(arr, idxs, i);
            }
        }

        return ans;
    }
};
// @lc code=end
